package cn.fansunion.leecode.math;

import java.util.ArrayList;
import java.util.List;

/**
 * 杨辉三角 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * 
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 https://leetcode-cn.com/problems/pascals-triangle/
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-18
 */
public class PascalsTriangle {

    /**
     * 严格按照定义，从上至下，从左到右；先判断一行的2个边界值都直接为1，不会出现数组越界的情况
     * 实践：一道简单题，改了3次，各种越界。主要是二维数组，行和列都需要从0开始，边界值判断容易搞错。
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> listList = new ArrayList<>();
        for (int row = 0; row < numRows; row++) {
            List<Integer> list1 = new ArrayList<>();
            for (int colIndex = 0; colIndex <= row; colIndex++) {
                if (colIndex == 0 || colIndex == row) {
                    list1.add(1);
                } else {
                    // array[row][colIndex]=array[row-1][colIndex-1]+array[row-1][colIndex]
                    final List<Integer> prevRow = listList.get(row - 1);
                    Integer num = prevRow.get(colIndex-1) + prevRow.get(colIndex);
                    list1.add(num);
                }
            }
            listList.add(list1);
        }
        return listList;

    }
}
